/*
 * @lc app=leetcode.cn id=744 lang=cpp
 *
 * [744] 寻找比目标字母大的最小字母
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <stdlib>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = letters.size();
        int left = 0,right = n-1;
        while(left < right) {
            int mid = (left + right)/2;
            if(letters[mid] > target) {
                right = mid;
            }else {
                left = mid+1;
            }
        }
        if(right == letters.size()-1 && letters[n-1] <= target) {
            return letters[0];
        }
        return letters[right];

        //一行
        //return letters[(upper_bound(letters.begin(),letters.end(),target)-letters.begin())%letters.size()];
    }
};
// @lc code=end

